/*
64. 最小路径和

暴力递归: 直接统计所有路径和的最小值， Leetcode超时
dp表:  与grid大小相同， dp记录每个row,col位置到右下角的最小路径和，其中是有规律的
        dp右下角的路径为grid右下角的值
        最后一行，只能往→走,dp[row][col] = grid[row][col] + dp[row][col+1]
        最后一列, 只能往↓走,dp[row][col] = grid[row][col] + dp[row+1][col]
        其他: dp[row][col] = grid[row][col] + min(dp右边, dp下边)
 */

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  return process(grid, 0, 0)
}

/**
 * 返回从(row,col)到右下角的最小路径权值和
 * @param {number[][]} grid
 * @param {number} row
 * @param {number} col
 * @return {number}
 */
function process (grid, row, col) {
  if (row === grid.length - 1 && col === grid[0].length - 1) {
    return grid[row][col]
  }
  if (row === grid.length - 1) {
    return grid[row][col] + process(grid, row, col + 1)
  }

  if (col === grid[0].length - 1) {
    return grid[row][col] + process(grid, row + 1, col)
  }
  const rightRes = grid[row][col] + process(grid, row, col + 1)
  const downRes = grid[row][col] + process(grid, row + 1, col)
  return Math.min(rightRes, downRes)
}

const arr = [[3, 8, 6, 0, 5, 9, 9, 6, 3, 4, 0, 5, 7, 3, 9, 3], [0, 9, 2, 5, 5, 4, 9, 1, 4, 6, 9, 5, 6, 7, 3, 2], [8, 2, 2, 3, 3, 3, 1, 6, 9, 1, 1, 6, 6, 2, 1, 9], [1, 3, 6, 9, 9, 5, 0, 3, 4, 9, 1, 0, 9, 6, 2, 7], [8, 6, 2, 2, 1, 3, 0, 0, 7, 2, 7, 5, 4, 8, 4, 8], [4, 1, 9, 5, 8, 9, 9, 2, 0, 2, 5, 1, 8, 7, 0, 9], [6, 2, 1, 7, 8, 1, 8, 5, 5, 7, 0, 2, 5, 7, 2, 1], [8, 1, 7, 6, 2, 8, 1, 2, 2, 6, 4, 0, 5, 4, 1, 3], [9, 2, 1, 7, 6, 1, 4, 3, 8, 6, 5, 5, 3, 9, 7, 3], [0, 6, 0, 2, 4, 3, 7, 6, 1, 3, 8, 6, 9, 0, 0, 8], [4, 3, 7, 2, 4, 3, 6, 4, 0, 3, 9, 5, 3, 6, 9, 3], [2, 1, 8, 8, 4, 5, 6, 5, 8, 7, 3, 7, 7, 5, 8, 3], [0, 7, 6, 6, 1, 2, 0, 3, 5, 0, 8, 0, 8, 7, 4, 3], [0, 4, 3, 4, 9, 0, 1, 9, 7, 7, 8, 6, 4, 6, 9, 5], [6, 5, 1, 9, 9, 2, 2, 7, 4, 2, 7, 2, 2, 3, 7, 2], [7, 1, 9, 6, 1, 2, 7, 0, 9, 6, 6, 4, 4, 5, 1, 0], [3, 4, 9, 2, 8, 3, 1, 2, 6, 9, 7, 0, 2, 4, 2, 0], [5, 1, 8, 8, 4, 6, 8, 5, 2, 4, 1, 6, 2, 2, 9, 7]]
/* const arr = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
] */
console.log(dpGetMiniPath(arr))

function dpGetMiniPath (grid) {
  const rows = grid.length
  const cols = grid[0].length
  const dp = new Array(rows)
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(cols)
  }
  for (let i = rows - 1; i >= 0; i--) {
    for (let j = cols - 1; j >= 0; j--) {
      if (i === rows - 1 && j === cols - 1) {
        dp[i][j] = grid[i][j]
      } else if (i === rows - 1) {
        // 最后一行
        dp[i][j] = grid[i][j] + dp[i][j + 1]
      } else if (j === cols - 1) {
        // 最后一列
        dp[i][j] = grid[i][j] + dp[i + 1][j]
      } else {
        dp[i][j] = grid[i][j] + Math.min(dp[i][j + 1], dp[i + 1][j])
      }
    }
  }
  return dp[0][0]
}
